package demo3;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-09-01
 * Time: 7:19
 */
public class TestDemo {

    //给你一个二维网格,从给(0,0)位置走到最右下角的位置,求出路径最短和

    //也就是依赖左边的值和上边的值
    public static int way1(int[][] m){
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        //首先0行不需要依赖其他,只依赖自己左边的值
        dp[0][0] = 0;
        for(int j = 1;j<col;++j){
            dp[0][j] = dp[0][j-1] + m[0][j];
        }
        for(int i = 1;i<row;++i){
            dp[i][0] = dp[i-1][0] + m[i][0];
            for(int j =1;j<col;++j){
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + m[i][j];
            }
        }
        return dp[row-1][col-1];
    }

    public static int way2(int[][] m){
        int row = m.length;
        int col = m[0].length;
        int[] arr = new int[col];
        //先填上第0行
        arr[0] = 0;
        for(int j =1;j< col;++j){
            arr[j] = arr[j-1] + m[0][j];
        }
        for(int i =1;i<row;++i){
            arr[0] += m[i][0];
            for(int j =1;j<col;++j){
                arr[j] = Math.min(arr[j-1],arr[j]) + m[i][j];
            }
        }
        return arr[col-1];
    }

    public static void main(String[] args) {

    }

}
